package com.heima.leetcode.datastructure.hashtable;

import java.util.HashMap;
import java.util.HashSet;

/**
 * <strong>判断数组中是否有重复元素 217</strong>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/26 15:28
 */
public class ContainsDuplicate {

    /**
     * <h3>方法一：用哈希表</h3>
     * @param nums 数组
     * @return 有重复元素返回true，否则返回false
     */
    public static boolean containsDuplicate1(int[] nums) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int num : nums) {
            if (hashMap.containsKey(num)){
                return true;
            }
            hashMap.put(num,num);
        }
        return false;
    }

    /**
     * <h3>方法二：用哈希集合</h3>
     * 优势在于每次都少调用一次containsKey方法
     * @param nums 数组
     * @return 返回true，表示有重复元素，否则返回false
     */
    public static boolean containsDuplicate2(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();
        for (int num : nums) {
            if (!hashSet.add(num)){
                return true;
            }
        }
        return false;
    }

    /**
     * <h3>方法三：用哈希表，模拟哈希集合的实现</h3>
     * 优势在于，不用调用containsKey方法，以及一些小优化
     * @param nums 数组
     * @return 返回true，表示有重复元素，否则返回false
     */
    public static boolean containsDuplicate3(int[] nums) {
        HashMap<Integer, Object> hashMap = new HashMap<>(nums.length * 2);
        Object o = new Object();
        for (int num : nums) {
            if (hashMap.put(num, o) != null){
                return true;
            }
        }
        return false;
    }
}
